\documentclass[11pt]{report}

%IMPORTANTE comando \hyphenation{ma-cro-istru-zio-ne nitro-idrossil-amminico} definisce all'algoritmo di latex come spezzare una parola non presente nel suo vocabolario!!

%INCLUSIONE DI PACCHETTI
\usepackage{graphicx}
\usepackage{rotating}
\usepackage{array}
\usepackage{longtable}
\usepackage{multirow}
\usepackage{wrapfig} 
\usepackage{lastpage}
\usepackage{fancyhdr}
\usepackage[english]{babel}
\usepackage{amssymb}
%\usepackage[T1]{fontenc}
%\usepackage[latin9]{inputenc}
\usepackage[colorlinks=true]{hyperref} %per indice con link alle pagine
\usepackage[a4paper,portrait,left=2.5cm,right=2.5cm,bindingoffset=5mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{color}
%\usepackage{xstring}
\hypersetup{colorlinks,citecolor=black,filecolor=black,linkcolor=red,urlcolor=blue}
\setcounter{secnumdepth}{2} % per numerare anche \subsubsection
\setcounter{tocdepth}{2}% per farlo apparire nell'indice
\frenchspacing
\definecolor{LightMagenta}{cmyk}{0.1,0.8,0,0.1}


%HEADER e FOOTER di tutte le pagine tranne quella in cui compare il titolo del capitolo
\pagestyle{fancy}
\fancyhead{}
\headheight = 54pt
\lhead{Computer Science Theory II}
\lfoot{}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
\rhead{\nouppercase{\leftmark}}
\renewcommand{\chaptermark}[1]{\markboth{\thechapter.\ #1}{}}

%HEADER e FOOTER della pagina dove compare il titolo del capitolo
\fancypagestyle{plain}{
%\lhead{\includegraphics[height=50pt]{images/logoUniPd.png}} %IN ALTO A SINISTRA (POTREBBE ANDARE BENE IL LOGO)
\chead{}
\rhead{\bfseries WS2011/12}%\manualeUtenteVer} %IN ALTO A DESTRA
\lfoot{
\begin{tabular}{lc}
Victor A. Arrascue Ayala & Mtr. 3209050\\
Tobias Domhan  & Mtr.  3202957 \\
\end{tabular}
}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
}

\fancypagestyle{romano}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

\fancypagestyle{empty}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

%PAGINA DI PRESETAZIONE DEL DOCUMENTO
\hyphenation{}
\begin{document}


%\begin{center}
%\thispagestyle{empty}
%\huge\textbf{UNIVERSIT\`A degli Studi di PADOVA}\\[2 cm] %GRUPPO DI APPARTENENZA
%\vspace*{0.5in}
%\LARGE\textbf{Titolo del documento}\\[1.0 cm] %TITOLO DEL DOCUMENTO
%\par\rule{10cm}{.5pt} \par
%{\large 12 Ottobre 2009}   %DATA DI CREAZIONE
%\par\rule{10cm}{.10pt} \par
%\vspace*{1.0in}
%\includegraphics[scale=0.30]{images/logoUniPd.png} \\[2cm] %LOGO GRUPPO
%\Large\textbf{Michele Tonon} %AUTORE
%\par\rule{6cm}{.5pt} \par
%\end{center}



% INDEX
%\newpage
%\thispagestyle{romano}
%\pagenumbering{arabic}
%\tableofcontents


%--------------------------------------------- 


%CONTENT


\newpage
\thispagestyle{plain}

\begin{center}
{\Large \textbf{Exercise Sheet 10}}
\end{center}

\noindent{\textbf{Exercise 10.1}}\\\\
First of all we assume that the exercise says that it has at least 2n-1 derivation steps, as we could always increase this number, by introducing unnecessary  rules to the grammar, that don't change the language, e.g. an addition to the tree that just evaluates to epsilon.\\\\
We'll prove this by induction.\\
\textbf{base case}:\\
As a base case we take a string with length n = 1. Because it must be in CNF it consists only of a terminal. This can be derived in a single step, from a rule of the kind: S$\rightarrow$a.\\
$2n-1=2-1=1$\\
Hence the formula holds for the base case.\\
\textbf{induction hypothesis}:\\
The IH is that a string n can be derived in 2n-1 steps, by a grammar in CNF.\\
That means we would expect a string of length n+1 to be derivable in 2(n+1)-1 steps.\\
\textbf{induction step}:\\
Suppose we have a string with length n, for which the IH holds. Now we add another terminal(let's call it x) symbol to the string. We assume that the string is still in the same language. Thus there exists a parse tree deriving it. Compared to the previous parse tree we need two additional steps.\\
One that goes from a variable (e.g. X) to the newly added terminal:\\ 
X$\rightarrow$x\\
Furthermore we need another step that adds this variable somewhere in the parse tree. This will be of the form:\\
A$\rightarrow$XY or A$\rightarrow$YX\\
so we get:\\
2n-1+2=2(n+1)-1\\\\
\textbf{q.e.d.}

\vspace{1cm}
\noindent{\textbf{Exercise 10.2}}\\\\
a)\\
The middle part only consists of b, so we get an equivalent language by switching both b parts:
$L_{1'}$ = \{$a^nb^nb^ma	^m \mid n,m \in \mathbb{N}	$\}\\
A grammar that accepts the given language is the following:\\
S $\rightarrow$ $S_2S_3$\\
$S_2 \rightarrow a S_2 b \mid \epsilon$\\
$S_3 \rightarrow b S_3 a \mid \epsilon$\\\\
b)\\
A grammar that accepts the given language is the following:\\
$S \rightarrow$ $S_1$\\
$S_1 \rightarrow a S_1 c \mid S_2 \mid \epsilon$\\
$S_2 \rightarrow b S_2 c \mid \epsilon$\\

\noindent{\textbf{Exercise 10.3}}\\\\
(a) A = \{a$^{n}$b$^{m}$c$^{n.m}$ $\mid$ n,m $\in$ $\mathbb{N}$\} is not a context-free grammar.\\
This will proved using the pumping lemma:\\
We choose s = a$^{p}$b$^{p}$c$^{p.p}$\\
Because of the second condition $\mid$vy$\mid$ $>$ 0, either v or y are not empty\\
We consider the following cases:\\
A) both v and y contain only one type of alphabet symbol:\\
Then uv$^{0}$xy$^{0}$z $\notin$ B.\\
B) either v and y contain more than one type of symbol:\\
Then uv$^{2}$xy$^{2}$z $\notin$ B (the order is not right anymore).
\\\\
(b) B = \{0$^{n}$1$^{n^2}$ $\mid$ n $\in$ $\mathbb{N}$\} is not a context-free grammar.\\
This will proved using the pumping lemma:\\
We choose s = 0$^{p}$1$^{p^2}$\\
Because of the second condition $\mid$vy$\mid$ $>$ 0, either v or y are not empty\\
We consider the following cases:\\
A) both v and y contain only one type of alphabet symbol:\\
Then uv$^{2}$xy$^{2}$z $\notin$ B.\\
B) either v and y contain more than one type of symbol:\\
Then uv$^{2}$xy$^{2}$z $\notin$ B (the order is not right anymore).
\\
\end{document}